public class TextDemo {
    public int compare (String version1, String version2) {
        // write code here
       int n1 = version1.length();
       int n2 = version2.length();
       int i = 0;
       int j = 0;
       while(i<n1 || j<n2){
           long num1 = 0;
           while(i<n1 && version1.charAt(i)!='.'){
               num1 = num1 * 10+(version1.charAt(i)-'0');
               i++;
           }
           i++;
           long num2 = 0;
           while(j<n2 && version2.charAt(j)!='.'){
               num2 = num2 * 10+(version2.charAt(j)-'0');
               j++;
           }
           j++;
           if(num1>num2){
               return 1;
           }else if(num1<num2){
               return -1;
           }
       }
       return 0;

    }
    public int reversePairs(int[]  nums){
        if(nums.length<2){
            return 0;
        }
        int[] copy = new int[nums.length];
        for(int i = 0;i<nums.length;i++){
            copy[i] = nums[i];
        }
        return reversePairs(copy,0,nums.length-1,new int[nums.length]);
    }
    private int reversePairs(int[] array,int left,int right,int[] tem){
        if(left==right){
            return 0;
        }
        int middle = left+(right-left)/2;
        int leftPairs = reversePairs(array,left,middle,tem);
        int rightPairs = reversePairs(array,middle+1,right,tem);
        if(array[middle]<=array[middle+1]){
            return leftPairs+rightPairs;
        }
        int countPairs = mergeAndCount(array,left,middle,right,tem);
        return leftPairs+rightPairs+countPairs;
    }
    private int mergeAndCount(int[] array,int left,int middle,int right,int[] tem){
        for(int i = left;i<=right;i++){
            tem[i] = array[i];
        }
        int i = left;
        int j = middle+1;
        int count = 0;
        for(int k = left;k<=right;k++){
            if(i==middle+1){
                array[k] = tem[j];
                j++;
            }else if(j==right+1){
                array[k] = tem[i];
                i++;
            }else if(tem[i]<=tem[i]){
                array[k] = tem[i];
                i++;
            }else{
                array[k] = tem[j];
                j++;
                count+=(middle-i+1);
            }
        }
        return count;
    }
    public int mod = 1000000007;
    public int InversePairs(int [] array) {
        int n = array.length;
        int[] res = new int[n];
        return mergeSort(0,n-1,array,res);
    }
    public int mergeSort(int left,int right,int[] data,int[] temp){
        if(left>=right){
            return 0;
        }
        int middle = (left+right)/2;
        int res = mergeSort(left,middle,data,temp)+mergeSort(middle+1,right,data,temp);
        res%=mod;
        int i = left;
        int j = middle+1;
        for(int k = left; k<=right;k++){
            temp[k] = data[k];
        }
        for(int k = left;k<=right;k++){
            if(i == middle+1){
                data[k] = temp[j++];
            }else if(j== right+1 || temp[i]<=temp[j]){
                data[k] = temp[i++];
            }else {
                data[k] = temp[i++];
                res += middle - i + 1;
            }
        }
        return res%mod;
    }
    public int findPeakElement (int[] nums) {
        // write code here
        int left = 0;
        int right = nums.length - 1;
        while(left < right){ //⼆分法
            int mid = (left + right) / 2;
            if(nums[mid] > nums[mid + 1])//右边是往下，不⼀定有坡峰
                right = mid-1;
            else//右边是往上，⼀定能找到波峰
                left = mid + 1;
        }
        return right; //其中⼀个波峰
    }
    public int findPeakElement1 (int[] nums) {
        // write code here
        int left = 0;
        int right = nums.length-1;
        while(left<right){
            int middle = left+(right-left)/2;
            if(compare(nums,middle-1,middle)==0 && compare(nums,middle,middle+1)!=0){
                return middle;
            }else if(compare(nums,middle,middle+1)==0){
                left = middle+1;
            }else{
                right = middle-1;
            }
        }
        return left;
    }
    private int compare(int[]nums,int index1,int index2){
        int[] array1 = get(nums,index1);
        int[] array2 = get(nums,index2);
        //当 一个 index==0 && 另一个index!=0
        if(array1[0]!=array2[0]){
            return array1[0]>0?1:0;
        }
        //index 都不是 下标0
        if(array1[0]==0){
            return 0;
        }
        return array1[1]>array2[1]?1:0;

    }
    private int[] get(int[] nums,int index){
        if(index==-1 || index ==nums.length){
            return new int[]{0,0};
        }
        return new int[]{1,nums[index]};
    }
    public static boolean Find1(int target, int [][] array) {
        for(int i = array.length-1;i>=0;i--){
            int j = 0;
            if(array[i].length>0 && array[i][j]<=target){
                while(i>=0 && j<array[i].length){
                    if(array[i][j]==target){
                        return true;
                    }else if(array[i][j]<target){
                        j++;
                    }else if(array[i][j]>target){
                        i--;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] array = new int[][]{{}};
        Find1(7,array);
    }
    public boolean Find(int target, int [][] array) {
        for(int i = 0;i<array.length;i++){
            int startIndex = 0;
            int lastIndex = array[i].length-1;

            if( startIndex<lastIndex && target>=array[i][startIndex] && target<=array[i][lastIndex]){
                if(findMiddle(array[i],target)!=-1){
                    return true;
                }
            }
        }
        return false;
    }
    private int findMiddle(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int middle = left+(right-left)/2;
            if(nums[middle]==target){
                return middle;
            }else if(nums[middle]<target){
                left = middle+1;
            }else{
                right = middle-1;
            }
        }
        return -1;
    }
}
